package de.rs.espresso.algorithms.minimumcover;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import de.rs.espresso.algorithms.minimumcover.model.Row;
import de.rs.espresso.tools.Statistics;

public class MaximumIndependentSet {

	List<Node> nodeList = new ArrayList<Node>();

	List<Node> clique = new ArrayList<Node>();

	private void initialize(List<Row> elements) {
		for (Row element : elements) {
			nodeList.add(new Node(element));
		}

		for (Node n : nodeList) {
			for (Node m : nodeList) {
				if (!(m == n))
					n.connect(m);
			}
		}
	}

	public List<Row> compute(List<Row> elements) {
		
		long id = Statistics.startMeasurement("MAXIMUM_INDEPENDENT_SET");

		clique = new ArrayList<Node>();

		initialize(elements);

		while (!clique.containsAll(nodeList)) {

			Node maxDegreeNode = getBestNextNode();

			clique.add(maxDegreeNode);

			clearConnections();

		}

		List<Row> result = new ArrayList<Row>();

		for (Node n : clique)
			result.add(n.getElement());

		Statistics.stopMeasurement(id);
		
		return result;

	}

	private Node getBestNextNode() {

		Collections.sort(nodeList, new Comparator<Node>() {

			@Override
			public int compare(Node o1, Node o2) {
				return -o1.getDegree() + o2.getDegree();
			}

		});

		List<Node> maxDegreeNodes = new ArrayList<Node>();
		int maxDegree = -1;
		for (Node n : nodeList) {
			if (!clique.contains(n)) {
				if (maxDegree == -1)
					maxDegree = n.getDegree();

				if (n.getDegree() == maxDegree)
					maxDegreeNodes.add(n);
				else
					break;
			}

		}

		maxDegree = 0;
		Node maxDegreeNode = null;
		for (Node n : maxDegreeNodes) {
			int sum = n.getConnectNodesDegreeSum();
			if (sum >= maxDegree) {
				maxDegree = sum;
				maxDegreeNode = n;
			}
		}

		return maxDegreeNode;

	}

	private void clearConnections() {

		List<Node> toRemove = new ArrayList<Node>();

		for (Node n : nodeList) {
			if (!clique.contains(n))
				for (Node m : clique) {
					if (!n.isConnected(m)) {
						toRemove.add(n);
					}
				}
		}

		for (Node n : toRemove) {
			nodeList.remove(n);
			n.removeConnections();
		}

	}

	public class Node {
		private List<Node> connectedNodes = new ArrayList<Node>();
		private Row element;

		public Node(Row element) {
			this.element = element;
		}

		public void connect(Node otherNode) {
			if (isDisjoint(otherNode))
				connectedNodes.add(otherNode);
		}

		private boolean isDisjoint(Node otherNode) {
			return !element.intersects(otherNode.getElement());
		}

		public Row getElement() {
			return element;
		}

		public int getDegree() {
			return connectedNodes.size();
		}

		public boolean isConnected(Node otherNode) {
			return connectedNodes.contains(otherNode);
		}

		public int getConnectNodesDegreeSum() {
			int sum = 0;
			for (Node n : connectedNodes) {
				sum += n.getDegree();
			}
			return sum;

		}

		public void removeConnections() {
			for (Node n : connectedNodes) {
				n.remove(this);
			}
		}

		private void remove(Node otherNode) {
			if (connectedNodes.contains(otherNode))
				connectedNodes.remove(otherNode);
		}

	}

	public static BitSet getVector() {

		return null;
	}

}
